class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        // 暴力法是时间复杂度O(N^2)，用前缀和思想是O(N)
        // 构造一个前缀和数组arr1和一个后缀和数组arr2，然后遍历比较
        int n = nums.size();
        vector<int> arr1(n, 0), arr2(n, 0);
        for(int left = 1, right = n-2; left < n; ++left, --right)
        {
            arr1[left] = arr1[left-1] + nums[left-1]; // arr1表示其左边的和，所以nums[left-1]
            arr2[right] = arr2[right+1] + nums[right+1]; // 构成后缀和
        }
        for(int i = 0; i < n; ++i)
        {
            if(arr1[i] == arr2[i])
            {
                return i;
            }
        }
        return -1;
    }
};